#include <stdio.h>
#include "seq_list.cpp"

int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

/// 注意!!!!
/// 这里是王道的答案 貌似有问题 这个二分法算出的值不对 周末再看看 先跳过

// 两个等长增序数组的中位数
int Getmiddle(SeqList &L1, SeqList &L2)
{
    // 奇数中位数是中间值
    // 偶数中位数是中间俩数的平均值
    int s1 = 0, e1 = L1.length - 1; // L1的开始和结尾
    int s2 = 0, e2 = L2.length - 1; // L2的开始和结尾
    int m1, m2;
    while (s1 != e1 || s2 != e2)
    {
        m1 = (s1 + e1) / 2;
        m2 = (s2 + e2) / 2;
        if (L1.data[m1] == L2.data[m2])
            return L1.data[m1];
        if (L1.data[m1] < L2.data[m2])
            if ((s1 + e1) % 2)
            {
                // 偶数
                s1 = m1 + 1;
                e2 = m2;
            }
            else
            {
                // 奇数
                s1 = m1;
                e2 = m2;
            }
        else
            if ((s2 + e2) % 2)
            {
                e1 = m1;
                s2 = m2 + 1;
            }
            else
            {
                e1 = m1;
                s2 = m2;
            }
    }
    return L1.data[s1] < L2.data[s2] ? L1.data[s1] : L2.data[s2];
}

int main()
{
    SeqList L1;
    int data1[10] = {6,7,8,9,10};
    L1.data = data1;
    L1.length = 5;

    SeqList L2;
    int data2[10] = {1,2,3,4,5};
    L2.data = data2;
    L2.length = 5;

    int mid = Getmiddle(L1,L2);
    printf("===> %d", mid);

    return 0;
}